package UF;

import java.util.TreeSet;

public class Solution {
    public interface UF {
        int getSize();

        boolean isConnected(int p, int q);

        void unionElements(int p, int q);
    }

    public class UnionFind2 implements UF {
        private int[] parent;

        public UnionFind2(int size) {
            parent = new int[size];

            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        @Override
        public int getSize() {
            return parent.length;
        }

        @Override
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }

        private int find(int p) {
            if(p < 0 || p >= parent.length){
                throw new IllegalArgumentException("p is out of bound.");
            }

            while(p != parent[p]) {
                p = parent[p];
            }

            return p;
        }

        @Override
        public void unionElements(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);

            if (pRoot == qRoot) {
                return;
            }

            parent[pRoot] = parent[qRoot];
        }
    }

    public int findCircleNum(int[][] M) {
        int n = M.length;

        UnionFind2 uf = new UnionFind2(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (M[i][j] == 1) {
                    uf.unionElements(i, j);
                }
            }
        }

        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            set.add(uf.find(i));
        }

        return set.size();
    }

    public static void main(String[] args) {
        int[][] M = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

        System.out.println((new Solution()).findCircleNum(M));
    }
}
